\subsection{Metodologia de Treinamento}

Cada uma das técnicas a serem exploradas passam por dois processos: treinamento e validação. Durante o treinamento, a técnica conhece a entrada e a saída esperada, de forma que é capaz de se ajustar para satisfazer a saída indicada. Já na validação, a técnica recebe uma entrada e precisa ser capaz de prever a saída. Caso a saída obtida da técnica seja diferente daquela apontada na base de dados, houve um erro na predição realizada pela técnica.

Para que a técnica não se vicie numa determinada base de dados, é adequado que a base de dados utilizada para treinamento seja distinta daquela usada para testes. Para tanto, uma boa estratégia é dividir toda a base de dados conhecida em duas: uma com as instâncias utilizadas para teste e outra com as instâncias utilizadas para treinamento. Esta divisão deve buscar também manter a representatividade de cada valor a ser obtido na saída. Por exemplo, deve-se tentar obter a mesma proporção de cada uma das letras tanto na base de treinamento como na de testes.

Kohavi~\cite{Kohavi1995} analisa três técnicas possíveis a serem usadas no processo de validação. Neste trabalho, discute-se a validação cruzada (\textit{k-fold}). Nela, a base de dados é particionada em $k$ novas base de dados. Então, $1$ parte é escolhida como base de teste e as outras $k - 1$ partes escolhidas como base de treinamento. Este processo é repetido $k$ vezes: cada vez selecionando uma parte diferente para ser tomada como base de testes. Kohavi discute como um valor pequeno de k pode aumentar a variância, enquanto um valor maior pode incentivar um viés (especialização na base de treinamento) da técnica analisada. O autor ainda discute sobre a importância de manter a proporção dos elementos em ambas as bases de treinamento e de teste e cita que a melhor análise e comparação entre duas técnicas validadas se dá pela múltipla execução da técnica com bases de dados de instâncias distintas.

Neste trabalho, serão utilizadas a validação cruzada \textit{10-fold} para a comparação dos melhores resultados obtidos de cada uma das técnicas.

\subsection{Descrição dos parâmetros e das técnicas}

Cada uma das três técnicas apresentadas apresenta parâmetros de configuração que precisam ser definidos antes do treinamento. Nesta sub-seção, serão discutidos a consequência do uso dos parâmetros existentes para cada uma das técnicas.

\subsubsection{Redes Bayesianas}

John e Langley~\cite{John1995} discutem a implementação de uma rede bayesiana simples. Nela, não são considerados eventuais relacionamentos entre os atributos de uma imagem que representa o caractere (ou seja: são eventos independentes), nem há atributos ocultos interferindo no resultado.

%TODO Observe que aqui "discretização supervisionada" está em português mas quando vai explicá-lo o destaque está em inglês "Supervised Discretization"
Dois parâmetros podem ser utilizados para a construção de uma rede bayesiana: uso do \textit{kernel estimator} e uso de \textit{Supervised Discretization}.
 
\textbf{Kernel Estimator}

A rede bayesiana faz uso de uma estimativa de probabilidade para cada atributo numérico existente. Normalmente, utiliza-se uma distribuição normal gerada a partir do cálculo da média e variância dos elementos encontrados.

Entretanto, ao utilizar um kernel estimator, a rede bayesiana faz uso de um estimador que leva em consideração cada um dos valores encontrados em cada atributo analisando a quantidade de vezes que este valor se repete na entrada de dados. Como exemplo, uma base de dados que apresente $5$ instâncias com os valores $[1, 1, 2, 2, 3]$ para um determinado atributo da letra K, terá como média $1.8$, desvio padrão de $0.84$ e probabilidades $0.3$, $0.46$ e $0.17$ para os valores $1$, $2$ e $3$ respectivamente (distribuição normal).

Ao considerar o número de vezes que o elemento aparece na base de dados, estas probabilidades são recalculadas dando peso maior àquelas que mais aparecem mesmo que seja um valor de pouca probabilidade por causa da distância com a média. Tomando como exemplo a mesma base de dados citada anteriormente, ela seria balanceada com o cálculo proporcional ao peso do valor na base de dados: $[0.3 \times 2/5, 0.46 \times 2/5, 0.17 \times 1/5]$, ou seja: $[0.12, 0.19, 0.03]$. Estes valores são normalizados retornando os valores de probabilidade $[0.38, 0.58, 0.03]$.
 
Utilizando este novo estimador, a rede bayesiana dará maior valor de probabilidade aos valores mais comuns, independente da sua posição em relação a média. Esta medida é mais representativa do que utilizar apenas a média e desvio padrão para cálculo da probabilidade.
 
\textbf{Supervised Discretization}

Outro parâmetro das redes bayesianas é o uso de discretização dos valores de entrada. Cada valor de entrada passa a ser categorizado por um intervalo numérico de acordo com a precisão utilizada pelo processo de discretização.

No caso de atributos numéricos inteiros na base de dados que descreve imagens que representam letras, cada atributo é discretizado em intervalos com precisão 1. Um exemplo de um atributo dividido em três intervalos: $[-\infty, 2.5]$, $[2.5, 4.5]$ e $[4.5, \infty]$.

O processo de discretização é, no entanto, supervisionado. Cada atributo é discretizado de forma a reduzir a entropia entre as classes existentes. Isto é significativo pois valores como $13$, $14$ e $15$, os maiores na base de dados de letras, podem ser discretizados e interpretados na rede bayesiana como um único valor. Isto permite a rede inferir generalizações do tipo: ``um valor alto neste atributo implica numa maior chance de que ele seja da letra T''. Observe que não mais é utilizado os respectivos valores, mas um intervalo.

\subsubsection{Árvores de Decisão}

A página Monk Tutorial~\cite{Monk2009} descreve a árvore de decisão J48, técnica utilizada neste trabalho. Este modelo de árvore de decisão oferece diversas estratégias de poda. A poda de uma árvore pode ser útil em dois aspectos: permite uma fácil visualização da árvore de decisão e possibilita eliminar resultados de especialização que tenham sido gerados durante o treinamento.

A poda utilizada pela técnica J48 pode ser descrita da seguinte forma: se os erros de classificação de um nó forem maior do que os erros encontrados na árvore como um todo, este nó é eliminado e as folhas propagadas para outro ramo.

\subsubsection{Redes Neurais}

Este trabalho aborda o modelo de rede neural multi-camada Perceptron. Neste modelo, a rede neural é composta de uma camada de entrada, uma camada de saída e uma ou mais camadas intermediárias. Cada camada contém um número específico de neurônios, como exemplo, na figura~\ref{fig:nn}, a rede dispõe de 7 neurônios na camada de entrada, 3 na camada intermediária e 1 na camada de saída. Devido a esta distribuição, esta rede também é conhecida como rede neural 7-3-1.

\begin{figure}[h!]
  \centering
  \includegraphics[scale=0.4, bb=0 0 428 352]{./images/neural_network.png}
  % neural_network.png: 428x352 pixel, 72dpi, 15.10x12.42 cm, bb=0 0 428 352
  \caption{Rede Neural 7-3-1}
  \label{fig:nn}
\end{figure}

Para modelar uma rede neural é preciso identificar as entradas e saídas desta rede neural. Considerando o reconhecimento de letras, uma rede neural precisa ter 16 neurônios de entrada (1 para cada atributo da imagem), e 26 neurônios de saída (1 para cada letra). Assim, ao alimentar a rede neural com uma determinada entrada, a rede neural retorna, para cada letra, a probabilidade da imagem ser daquele caractere. Determinar o número de nós na camada intermediária não é algo preciso e será discutido mais adiante.

A rede neural precisa primeiro determinar como cada neurônio reage a um estímulo. Isto ocorre através de duas medidas: a taxa de aprendizagem e o momentum. Durante a etapa de treinamento, a rede neural recebe um estímulo de uma imagem de uma letra conhecida. A rede neural analisa então cada neurônio de saída identificado aqueles que cometeram um erro de classificação e os pesos dos neurônios de saída são corrigidos. Em seguida, esta diferença de erro é propagada para as camadas anteriores, onde os neurônios, a partir desta diferença, tentam corrigir o peso que deram a determinado estímulo. Esta correção é proporcional à taxa de treinamento (quanto mais alto, maior diferença do novo peso para o peso antigo).

De acordo com Orr~\cite{Orr1999},  momentum é um acréscimo a esta estratégia: além da variação ocasionada pela taxa de treinamento, adiciona-se ao peso a última variação do peso do neurônio multiplicado pelo momentum. A idéia disso é de que como o peso é alterado pela taxa de aprendizado, este termo adicionado impede que haja um deslocamento maior do que a medida necessária. O momentum também permite a convergência, na medida de que a variação da correção do peso tenderia a diminuir numa rede neural convergente.

Considerando esta fundamentação teórica, serão discutidos três parâmetros ajustáveis numa rede neural: o número máximo de iterações, a taxa de aprendizado e o número de nós na camada intermediária.

\textbf{Quantidade máxima de iterações}

Dada uma base de treinamento da rede neural, é possível passar várias vezes pela mesma base de treinamento buscando adaptar os pesos dos neurônios para se adequar as entradas fornecidas. Entretanto, cada passagem representa um custo de processamento associado em que, não necessariamente, processar as entradas repetitivamente ou até mesmo processar todas as entradas implica em melhorar significativamente a rede. Skapura~\cite{Skapura1995} discute esta relação.

Para uma base em que os dados estejam bem distribuídos e que os atributos a serem analisados não apresentam valores divergentes dentro de cada classe que se deseja obter na saída, não há vantagem em usar um número de iterações maior do que a medida da própria base de treinamento. No entanto, um valor pequeno não é suficiente para obter um suficiente treinamento. No exemplo do reconhecimento de letras, com 26 possíveis saídas, não adianta treinar com pelo menos 26 instâncias: 1 para cada classe, do contrário, a inferência não se faria significativa. Para 100 iterações, espera-se obter, em média, 4 instâncias para cada letra. Se estas forem representativas de toda amostra, esta quantidade de iterações seria suficiente.

Em geral, o número de iterações é uma medida que serve como limite superior, as redes neurais podem fazer uso do erro geral obtido como medida para parar o treinamento de uma rede neural. Por exemplo, poderia-se parar o treinamento de uma rede neural quando esta tivesse um erro de 5\%.

\textbf{Taxa de aprendizado}

A variação da taxa de aprendizado é outra medida a ser considerada durante o treinamento de uma rede neural. Já discutiu-se o significado da taxa de aprendizado. Entretanto, a taxa de aprendizado relaciona-se diretamente com a medida de momentum como apresenta Orr~\cite{Orr1999}. Com o momentum vai adicionar o fator de variação entre o peso atual e o peso anterior, uma elevada taxa de aprendizado com um alto valor de momentum pode fazer com que a rede neural divirja: a variação torna-se excessiva, impedindo a convergência.

No entanto, uma baixa taxa de aprendizado pode significar uma baixa conversão, implicando na necessidade de mais iterações. Assim, devem ser consideradas no cálculo da taxa de aprendizado:
  
\textbf{Quantidade de neurônios intermediários da rede}

Um dos parâmetros mais complexos de se estimar e explorar numa rede neural é o número de nós intermediários numa rede. Grande fonte desta dificuldade está no fato de que a literatura apresenta diversas sugestões de um valor inicial apropriado para o número de nós intermediários. Uma compilação de valores iniciais sugeridos pode ser encontrada na internet~\cite{Faq2009}:
    \begin{itemize}
      \item Um valor entre o número de nós na camada de entrada e o número de nós na camada de saída;
      \item A soma do número de nós na entrada e número de nós de saída multiplicado por $2/3$;
      \item Um valor menor que o número de nós na camada de entrada;
      \item Um valor menor do que o dobro do número de nós na camada de entrada;
      \item Igual a quantidade de componentes (atributos e relacionamentos) que capturem boa parte do conjunto de validação.
    \end{itemize}

Dieterle~\cite{Dieterle2003} apresenta outro aspecto do número de nós na camada intermediária: um elevado número de nós pode ocasionar uma especialização nos dados de treinamento, o que significa que a rede neural não é capaz de generalizar para os casos fora da base de treinamento. Assim, uma medida muito alta pode diminuir a qualidade da rede neural.